package LeetCode.leetcode106;


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        //为空
        if (postorder.length == 0)
            return null;
        int divide = postorder[postorder.length - 1];
        TreeNode root = new TreeNode(divide);
        //如果只有一个节点直接返回
        if (postorder.length == 1)
            return root;
        //在前序遍历中寻找分界位置
        int divideIndex = 0;
        for (; divideIndex < inorder.length; divideIndex++) {
            if (inorder[divideIndex] == divide)
                break;
        }
        int[] inorderLeft = new int[divideIndex];
        int[] postorderLeft = new int[divideIndex];
        //左边的两个
        for (int i = 0; i < divideIndex; i++) {
            inorderLeft[i] = inorder[i];
        }
        for (int i = 0; i < divideIndex; i++) {
            postorderLeft[i] = postorder[i];
        }

        //右边
        int[] inorderRight = new int[inorder.length - divideIndex - 1];
        int[] postorderRight = new int[inorder.length - divideIndex - 1];
        for (int i = divideIndex + 1, j = 0; i < inorder.length; i++, j++) {
            inorderRight[j] = inorder[i];
        }
        for (int i = divideIndex, j = 0; i < postorder.length - 1; i++, j++) {
            postorderRight[j] = postorder[i];
        }
        //左边递归
        root.left = buildTree(inorderLeft, postorderLeft);
        //右边递归
        root.right = buildTree(inorderRight, postorderRight);
        return root;
    }
}
